package leecode

func combinationSumLCR(candidates []int, target int) (result [][]int) {
	var backtracking func(candidates []int, startIndex int)
	path := make([]int, 0, len(candidates))
	backtracking = func(candidates []int, startIndex int) {
		//递归终止条件
		if target <= 0 {
			if target == 0 {
				temp := make([]int, len(path))
				copy(temp, path)
				result = append(result, temp)
				return
			}
			return
		}
		for i := startIndex; i < len(candidates); i++ {
			path = append(path, candidates[i])
			target = target - candidates[i]
			backtracking(candidates, i)
			//回溯
			path = path[:len(path)-1]
			target = target + candidates[i]
		}
	}
	backtracking(candidates, 0)
	return
}
